#include <bits/stdc++.h>
using namespace std;

template <typename K, typename V>
struct AVLTreeNode
{
    AVLTreeNode(const pair<K, V> &kv)
        : _left(nullptr), 
        _right(nullptr), 
        _parent(nullptr), 
        _kv(kv), 
        _bf(0)
    {
    }
    /* data */

    struct AVLTreeNode<K, V> *_left;
    struct AVLTreeNode<K, V> *_right;
    struct AVLTreeNode<K, V> *_parent;

    pair<K, V> _kv;
    int _bf;
};
template <typename K, typename V>
class AVLTree
{
    typedef AVLTreeNode<K, V> Node;
    
public:
    bool insert(const pair<K, V> &kv)
    {
        if (_root == nullptr)
        {
            _root = new Node(kv);
            return true;
        }
        Node *cur = _root;
        Node *parent = nullptr;
        while (cur)
        {
            if (cur->_kv.first < kv.first)
            {
                parent = cur;
                cur = cur->_right;
            }
            else if (cur->_kv.first > kv.first)
            {
                parent = cur;
                cur = cur->_left;
            }
            else
            {
                return false;
            }
        }
        cur = new Node(kv);
        if (kv.first > parent->_kv.first)
        {
            parent->_right = cur;
        }
        else
        {
            parent->_left = cur;
        }
        cur->_parent = parent;
        //更新平衡因子
        while (parent)
        {
            if (cur == parent->_right)
            {
                parent->_bf++;
            }
            else
            {
                parent->_bf--;
            }
            if (parent->_bf == 0)
            {
                break;
            }
            else if (abs(parent->_bf) == 1)
            {
                parent = parent->_parent;
                cur = cur->_parent;
            }
            else if (abs(parent->_bf) == 2)
            {
                //不平衡，需进行旋转
                //右子树高时需左旋
                if (parent->_bf == 2 && cur->_bf == 1)
                {
                    rotateL(parent);
                }
                else if (parent->_bf == -2 && cur->_bf == -1)
                {
                    rotateR(parent);
                }
                else if (parent->_bf == -2 && cur->_bf == 1)
                {
                    rotateLR(parent);
                }
                else if (parent->_bf == 2 && cur->_bf == -1)
                {
                    rotateRL(parent);
                }
                else
                {
                    assert(false);
                }
                break;
            }
            else
            {
                assert(false);
            }
        }
        return true;
    }
    
    void InOrder()
    {
        _InOrder(_root);
        cout << endl;
    }
    bool isBlance(){
        return _isBlance(_root);
    }
private:
    bool _isBlance(Node* root){
        if(root == nullptr){
            return true;
        }
        int leftH = height(root->_left);
        int rightH = height(root->_right);

        int diff = rightH - leftH;
        if (diff != root->_bf)
        {
            cout << root->_kv.first << "的平衡因子异常，为" << root->_bf << "应为：" << diff << endl;
            return false;
        }
        return abs(diff) < 2 && _isBlance(root->_left) && _isBlance(root->_right);
    }
    int height(Node* root){
        if(root == nullptr){
            return 0;
        }
        return 1 + max(height(root->_left), height(root->_right));
    }
    void _InOrder(Node *root)
    {
        if (root == nullptr)
        {
            return;
        }
        _InOrder(root->_left);
        std::cout << root->_kv.first << " " << root->_kv.second << endl;
        _InOrder(root->_right);
    }
    void rotateL(Node *root)
    {
        Node *rootR = root->_right;
        Node *rootRL = rootR->_left;

        root->_right = rootRL;
        if (rootRL)
        {
            rootRL->_parent = root;
        }
        Node *rootParent = root->_parent;

        rootR->_left = root;
        root->_parent = rootR;
        if (root == _root)
        {
            _root = rootR;
            rootR->_parent = nullptr;
        }
        else
        {
            if (root == rootParent->_left)
            {
                rootParent->_left = rootR;
            }
            else
            {
                rootParent->_right = rootR;
            }
            rootR->_parent = rootParent;
        }

        root->_bf = rootR->_bf = 0;
    }
    void rotateR(Node *root)
    {
        Node *rootL = root->_left;
        Node *rootLR = rootL->_right;

        root->_left = rootLR;
        if (rootLR)
        {
            rootLR->_parent = root;
        }
        Node *rootParent = root->_parent;

        rootL->_right = root;
        root->_parent = rootL;
        if (root == _root)
        {
            _root = rootL;
            rootL->_parent = nullptr;
        }
        else
        {
            if (rootParent->_left == root)
            {
                rootParent->_left = rootL;
            }
            else
            {
                rootParent->_right = rootL;
            }
            rootL->_parent = rootParent;
        }
        root->_bf = rootL->_bf = 0;
    }
    void rotateLR(Node *root)
    {
        Node *rootL = root->_left;
        Node *rootLR = rootL->_right;

        int bf = rootLR->_bf;
        rotateL(root->_left);
        rotateR(root);
        rootLR->_bf = 0;
        if (bf == 1)
        {
            rootL->_bf = -1;
            root->_bf = 0;
        }
        else if (bf == -1)
        {
            rootL->_bf = 0;
            root->_bf = 1;
        }
        else if (bf == 0)
        {
            rootL->_bf = root->_bf = 0;
        }
    }
    void rotateRL(Node *root)
    {
        Node *rootR = root->_right;
        Node *rootRL = rootR->_left;

        int bf = rootRL->_bf;
        rotateR(root->_right);
        rotateL(root);
        rootRL->_bf = 0;
        if (bf == 1)
        {
            rootR->_bf = 0;
            root->_bf = -1;
        }
        else if (bf == -1)
        {
            rootR->_bf = 1;
            root->_bf = 0;
        }
        else if (bf == 0)
        {
            root->_bf = rootR->_bf = 0;
        }else{
            assert(false);
        }
    }

private:
    Node *_root = nullptr;
};
